"""
@Desc: 0-1背包问题的动态规划求解方法
@Date: 2020/10/3
"""

import argparse


def get_args():
    ap = argparse.ArgumentParser()
    ap.add_argument('-c', '--capacity', type=int, default=11,
                    help='Capacity of knapsack problem')
    ap.add_argument('-n', '--numbers', type=int, default=5,
                    help='Goods numbers of knapsack problem')
    ap.add_argument('-w', '--weights', default='1,2,5,6,7',
                    help='Weights of goods, str type and split comma')
    ap.add_argument('-v', '--values', default='1,6,18,22,28',
                    help='Values of goods, str type and split comma')

    return ap.parse_args()


def parse_args():
    args = get_args()
    capacity = int(args.capacity)
    n = int(args.numbers)
    w_str = args.weights
    v_str = args.values

    # 为了便于算法实现，重量和价值数组第0个元素赋值为0
    weights = [0] + [int(item) for item in w_str.split(',')]
    values = [0] + [int(item) for item in v_str.split(',')]

    return capacity, n, weights, values


def knapsack():
    # 1. 解析输入参数，分别为：背包容量，商品数量，各商品重量，各商品价值
    capacity, n, weights, values = parse_args()

    # 2. 定义状态数组c，长度为背包容量大小+1
    c = [0 for _ in range(capacity + 1)]

    # 3. 动态规划求解
    # 商品序号从1,2, ..., n；尝试放置每一个商品至背包
    print('capacity    : ', [_ for _ in range(capacity + 1)])
    print('weight value: ', c)
    for i in range(1, n + 1):
        # 容量序号从capacity, capacity-1, ..., 1；倒叙是为了保证每个物品仅被使用一次
        for w in range(capacity, weights[i] - 1, -1):
            # 公式3.2状态转移方程
            c[w] = max(c[w - weights[i]] + values[i], c[w])

        # 打印每行状态值
        w_v_str = str(weights[i]) + 6 * ' ' + str(values[i])
        w_v_str = w_v_str + (12 - len(w_v_str)) * ' ' + ': '
        print(w_v_str, c)


def main_enter():
    knapsack()


if __name__ == '__main__':
    main_enter()
